Non decreasing array

Time: O(N); Space: O(1); easy

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: nums = [4, 2, 3]

Output: True

Explanation:

• You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4, 2, 1]

Output: False

Explanation:

• You can’t get a non-decreasing array by modify at most one element.

Notes:

• 1 <= n <= 10 ^ 4

• -10 ^ 5 <= nums[i] <= 10 ^ 5

class Solution1(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        modified, prev = False, nums[0]
        for i in range(1, len(nums)):
            if prev > nums[i]:
                if modified:
                    return False
                if i-2 < 0 or nums[i-2] <= nums[i]:
                    prev = nums[i]
                modified = True
            else:
                prev = nums[i]
        return True

s = Solution1()
nums = [4, 2, 3]
assert s.checkPossibility(nums) == True
nums = [4, 2, 1]
assert s.checkPossibility(nums) == False

See also:

https://leetcode.com/problems/non-decreasing-array/